ONI 1997, Finala, Timisoara
CLASA a XI-A
ZIUA 2, PROBLEMA 4
Panza de paianjen

Un paianjen isi tese panza ca in figura de mai jos:

	Nodurile acestei panze de paianjen vor fi plasate in directiile 
0,1,2,...,n. De asemenea, o astfel de panza are m niveluri concentrice de fire.
	Odata cu trecerea timpului, unele fire se destrama, iar paianjenul 
nu mai poate sa treaca pe acestea. Paianjenul "locuieste" in centrul 
panzei. Cunoscand care sunt firele destramate, precum si pozitia unei 
muste prinse in plasa, sa se determine cea mai scurta cale pe care 
trebuie sa o strabata paianjenul (masurata n numar de fire) pentru a 
ajunge la musca.
DATE DE INTRARE:
	Fisierul de intrare de tip text INPUT.TXT va avea urmatoarea structura:
	- pe prima linie sunt scrise doua numere: n, (n<=100) si m(m<=100) 
avand semnificatiile de mai sus;
	- pe a doua linie sunt scrise doua numere separate printr-un spatiu, 
reprezentand pozitia mustei (precizata prin numarul directiei si numarul 
nivelului pe care se afla);
	- urmatoarele linii descriu starea panzei: pe fiecare linie sunt 
descrise doua noduri intre care panza este destramata; fiecare nod este 
precizat printr-o pereche de numere: numarul de ordine al directiei si 
numarul de ordine al nivelului.

DATE DE IESIRE:
	Fisierul text OUTPUT.TXT va contine:
	- pe prima linie se va scrie un numar intreg, reprezentand lungimea 
drumului parcurs de paianjen;
	- pe urmatoarele linii se va afla descrierea nodurilor prin care trece 
paianjenul pentru a ajunge la musca (un nod pe o linie). Fiecare nod se 
precizeaza prin doua numere separate printr-un spatiu. Primul 
reprezinta directia, al doilea reprezinta nivelul pe care se afla nodul.
Observatii:
	- se considera ca paianjenul ramane agatat in panza, chiar si in cazul 
limita in care aceasta se destrama in totalitate;
	- daca nu exista solutie, in fisierul de iesire se va scrie: "NU";
	- daca exista mai multe solutii, atunci in fisierul de iesire se va 
scrie doar una.
Exemplu:
INPUT.TXT	OUTPUT.TXT

4 5		4
0 4		0 0
2 1 0 0	0 1
2 1 2 2	0 2
1 1 2 1	0 3
3 1 2 1	0 4
			
Timp maxim de executare pentru un test: 5 secunde.
=============================
Solutie (Clara Ionescu)
program panza;
  type lista=^art;
       art=record
             directie,nivel:integer;
             urm,pred:lista
           end;
  const x:array[1..4] of shortint=(0,0,1,-1);
        y:array[1..4] of shortint=(1,-1,0,0);
  var mat:array[0..102,0..102] of integer;
      rupte:array[1..5000,1..4] of integer;
      fi,fo:text;
      n,m,i,j,k,musca_dir,musca_nivel,nivel_nou,directie_noua,t:integer;
      cap,p,q,r,start,stop:lista;
      gasit,blocaj:boolean;

  function ExistaDrum(i1,i2,i3,i4:integer):boolean;
    var i:integer;
  begin
    ExistaDrum:=true;
    for i:=1 to k do
      if ((i1=rupte[i,1]) and (i2=rupte[i,2]) and (i3=rupte[i,3])
                          and (i4=rupte[i,4])) or
         ((i1=rupte[i,3]) and (i2=rupte[i,4]) and (i3=rupte[i,1])
                          and (i4=rupte[i,2]))
      then begin ExistaDrum:=false; exit end
  end;

  procedure Reconstituie(q:lista);
  begin
    if not ((q^.directie=0) and (q^.nivel=0))
    then Reconstituie(q^.pred);
    writeln(fo,q^.directie,' ',q^.nivel)
  end;

begin
  assign(fi,'INPUT.TXT'); reset(fi);
  readln(fi,n,m); readln(fi,musca_dir,musca_nivel);
  k:=0;
  while not seekeof(fi) do
  begin
    inc(k);
    readln(fi,rupte[k,1],rupte[k,2],rupte[k,3],rupte[k,4])
  end;
  close(fi);
  assign(fo,'OUTPUT.TXT'); rewrite(fo);
  inc(n);
  for i:=1 to n do
    for j:=1 to m do mat[i,j]:=0;
  gasit:=false; blocaj:=false;
  new(start);
  start^.urm:=nil; start^.pred:=nil; start^.directie:=0; start^.nivel:=0;
  if (musca_dir=0) and (musca_nivel=0)
  then p:=start
  else begin
         stop:=start;
         i:=0; gasit:=false;
         while not gasit and (i<=n-1) do
         begin
           if ExistaDrum(0,0,i,1)
           then
             begin
               new(q); q^.urm:=nil; q^.pred:=start; q^.directie:=i; q^.nivel:=1;
               stop^.urm:=q; stop:=stop^.urm;
               mat[i,1]:=1;
               if (q^.directie=musca_dir) and (q^.nivel=musca_nivel)
               then gasit:=true
             end;
           inc(i)
         end;
         if start^.urm=nil
         then blocaj:=true
         else
           begin
             start:=start^.urm;
             while not gasit and not blocaj do
               begin
                 blocaj:=true;
                 q:=start; t:=0; p:=stop;
                 while ((q<>stop) or (t=0)) and not gasit and (t=0) do
                   begin
                     for j:=1 to 4 do
                       begin
                         nivel_nou:=q^.nivel+y[j];
                         directie_noua:=q^.directie+x[j];
                         if (nivel_nou<>0) and (nivel_nou<=m)
                         then
                           if directie_noua>=0
                           then
                             if (mat[directie_noua mod n,nivel_nou]=0) and
                             ExistaDrum(q^.directie,q^.nivel,directie_noua mod n,nivel_nou)
                             then
                               begin
                                 new(r); r^.pred:=q; r^.urm:=nil;
                                 r^.directie:=directie_noua mod n;
                                 r^.nivel:=nivel_nou;
                                 p^.urm:=r;  p:=r;
                                 mat[directie_noua mod n,nivel_nou]:=mat[q^.directie,q^.nivel]+1;
                                 blocaj:=false;
                                 if (directie_noua mod n=musca_dir) and (nivel_nou=musca_nivel)
                                 then gasit:=true;
                               end
                             else
                         else
                          if (mat[n-1,nivel_nou]=0) and
                          ExistaDrum(q^.directie,q^.nivel,n-1,nivel_nou)
                          then
                            begin
                              new(r); r^.pred:=q; r^.urm:=nil;
                              r^.directie:=n-1; r^.nivel:=nivel_nou;
                              p^.urm:=r;  p:=r;
                              mat[n-1,nivel_nou]:=mat[q^.directie,q^.nivel]+1;
                              if (n-1=musca_dir) and (nivel_nou=musca_nivel)
                              then gasit:=true;
                              blocaj:=false
                            end
                       end;
                     if q=stop then t:=1;
                     if not gasit then q:=q^.urm
                   end;
                 start:=stop^.urm; stop:=p
               end
           end;
       end;
  if blocaj then writeln(fo,'NU')
  else
    begin
      writeln(fo,mat[musca_dir,musca_nivel]);
      Reconstituie(p)
    end;
  close(fo)
end.
------------------------------
